// https://leetcode.cn/problems/minesweeper/description/

// 算法思路总结：
// 1. 深度优先搜索实现扫雷游戏点击逻辑
// 2. 点击地雷'M'直接变为'X'（游戏结束）
// 3. 点击空白'E'时统计周围8方向地雷数量
// 4. 无相邻地雷时显示'B'并递归展开相邻格子
// 5. 有相邻地雷时显示相应数字
// 6. 时间复杂度：O(m×n)，空间复杂度：O(m×n)

#include <iostream>
using namespace std;

#include <cstring>
#include <vector>
#include <algorithm>

class Solution 
{
public:
    int m, n;
    int dx[8] = {-1, -1, 0, 1, 1, 1, 0, -1}, dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};
    bool vis[51][51];

    int getMineNums(vector<vector<char>>& board, int a, int b)
    {
        int ret = 0;
        for (int i = 0 ; i < 8 ; i++)
        {
            int x = a + dx[i], y = b + dy[i];
            if (x >= 0 && y >= 0 && x < m && y < n && (board[x][y] == 'M' || board[a][b] == 'X'))
            {
                ret++;
            }
        }
        return ret;
    }

    vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) 
    {
        m = board.size(), n = board[0].size();
        memset(vis, 0, sizeof(vis));

        dfs(board, click[0], click[1]);

        return board;
    }

    void dfs(vector<vector<char>>& board, int a, int b)
    {
        if (board[a][b] == 'M')
        {
            board[a][b] = 'X';
            return ;
        }

        int MineNums = getMineNums(board, a, b);
        if (board[a][b] == 'E')
        {
            if (MineNums == 0)
            {
                board[a][b] = 'B';
                for (int i = 0 ; i < 8 ; i++)
                {
                    int x = a + dx[i], y = b + dy[i];
                    if (x >= 0 && y >= 0 && x < m && y < n)
                    {
                        dfs(board, x, y);
                    }
                }
            }
            else
            {
                board[a][b] = MineNums + '0';
            }
        }
    }

    void printBoardSimple(const vector<vector<char>>& board) 
    {
        cout << "扫雷棋盘：" << endl;
        for (const auto& row : board) 
        {
            for (char c : row) 
            {
                cout << c << " ";  
            }
            cout << endl;
        }
    }
};

int main()
{
    vector<vector<char>> board1 = {
        {'E','E','E','E','E'},
        {'E','E','M','E','E'},
        {'E','E','E','E','E'},
        {'E','E','E','E','E'}
    };
    vector<int> click1 = {3, 0};
    
    vector<vector<char>> board2 = {
        {'B','1','E','1','B'},
        {'B','1','M','1','B'},
        {'B','1','1','1','B'},
        {'B','B','B','B','B'}
    };
    vector<int> click2 = {1, 2};

    Solution sol;

    auto vv1 = sol.updateBoard(board1, click1);
    auto vv2 = sol.updateBoard(board2, click2);

    sol.printBoardSimple(board1);
    sol.printBoardSimple(board2);

    return 0;
}